package com.dyz.leetcode._01_array;

import java.util.ArrayList;
import java.util.List;

public class _1002_commonChars {
    // 时间复杂度：O(m*n)，m 表示数组的长度，n 表示每个字符串的平均长度
    public List<String> commonChars(String[] words) {

        List<String> res = new ArrayList();
        int [] minfrq = new int[26];
        //计算第一个单词的频次
        for(char c : words[0].toCharArray()){
            minfrq[c-'a'] +=1;
        }

        //两层遍历循环，计算每次出现最小频次
        for(int i=0; i<words.length; i++){
            char[] chars = words[i].toCharArray();
            int[] freq = new int[26];
            for(int j=0; j<chars.length; j++){
                freq[chars[j]-'a']+=1;
            }

            //求共有最小值
            for(int m=0; m<26; m++){
                minfrq[m] = Math.min(minfrq[m], freq[m]);
            }
        }

        // 将字符出现最小次数大于 0 的字符输出到结果中,注意，可能是多次出现同个字母
        for(int i=0; i<26;i++){//字母位置
            for(int j=minfrq[i]; j>0; j--){  //次数
                res.add(String.valueOf((char)(i+'a')));
            }

        }
        return res;
    }
}
